class Solution {
public:
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
        unordered_map<int, vector<int>> ump;
        unordered_map<int, int> cnt;
        unordered_map<int, int> vis;
        for (auto &pair: adjacentPairs) {
            ump[pair[0]].push_back(pair[1]);
            ump[pair[1]].push_back(pair[0]);
            cnt[pair[0]]++;
            cnt[pair[1]]++;
        }
        vector<int> res;
        for (auto &[k, v]: cnt) {
            if (v == 1) {
                int from = k;
                int eleNum = 1;
                res.push_back(from);
                vis[from] = 1;
                while (eleNum < adjacentPairs.size() + 1) {
                    if (ump[from].size() == 1) {
                        res.push_back(ump[from][0]);
                        from = ump[from][0];
                    } else if (vis[ump[from][0]] == 0) {
                        res.push_back(ump[from][0]);
                        from = ump[from][0];
                    } else {
                        res.push_back(ump[from][1]);
                        from = ump[from][1];
                    }
                    vis[from] = 1;
                    eleNum++;
                }
                break;
            }
        }
        return res;
    }
};